/**
 * 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
 * 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
 * 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
 * 最后返回经过上色渲染后的图像。
 */
/**
 * 示例：输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
 * 输出: [[2,2,2],[2,2,0],[2,0,1]]
 * 
 * 解释：给一个矩阵表示图像，给一个像素坐标和新颜色，把坐标上下左右反向的旧颜色变成新的，依次递归到没有点的颜色要改
 */

#include<vector>
using namespace std;

// 深度优先DFS
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        // 先获取旧颜色
        int oldColor = image[sr][sc];
        DFS(image,sr, sc, newColor, oldColor);
        return image;
    }
    
    void DFS(vector<vector<int>>& image, int sr, int sc, int newColor, int oldColor){
        if(sr<0 || sr>=image.size() || sc<0 || sc>=image[0].size()){
            return;
        }

        // image[sr][sc] == newColor是为了防止原颜色和新颜色一样，就会无限递归，然后爆栈
        // 如果新旧颜色相同，经过一圈又回到起点，如果只有if(image[x][y] != oldColor） ，但此时的颜色是（1），即便赋予其新颜色也还是（1），是同旧颜色一样。那么这个判断条件就相当于失效了，即不能正常 return。 那么便会重新对其赋予新颜色，然后查看其上下左右。
        // 这样就会陷入无限的从开始坐标循环到开始坐标的过程，最终爆栈
        if(image[sr][sc] != oldColor || image[sr][sc] == newColor){
            return;
        }

        image[sr][sc] = newColor;
        DFS(image, sr-1, sc, newColor, oldColor);
        DFS(image, sr+1, sc, newColor, oldColor);
        DFS(image, sr, sc-1, newColor, oldColor);
        DFS(image, sr, sc+1, newColor, oldColor);
    }
};